package com.sh.algorithm.offers;

import com.sh.algorithm.ListNode;

import java.util.Stack;

/**
 * @author veviz
 * @description 两个链表的第一个公共节点
 * @create 2020-03-08 23:13
 */
public class Solution52 {
    /**
     * 这是用两个栈来实现的，不过还有更加巧妙的方法
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack<ListNode>();
        Stack<ListNode> stackB = new Stack<ListNode>();
        while (headA != null){
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null){
            stackB.push(headB);
            headB = headB.next;
        }
        ListNode preNode = null;
        while (!stackA.isEmpty() && !stackB.isEmpty()){
            if (!stackA.peek().equals(stackB.peek())){
                return preNode;
            }
            preNode = stackA.pop();
            stackB.pop();
        }
        return preNode;
    }

    /**
     * 双指针算法，浪漫相遇
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNodeV2(ListNode headA, ListNode headB) {
         ListNode p1 = headA;
         ListNode p2 = headB;
         while (p1 != p2){
             p1 = p1 != null ? p1.next : headA;
             p2 = p2 != null ? p2.next : headB;
         }
         return p1;
    }
}
